package problem692;

// 692.前k个高频单词
// https://leetcode.cn/problems/top-k-frequent-words/

import java.util.*;

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        //1.统计每个单词出现的次数
        HashMap<String, Integer> map = new HashMap<>();
        for(String word: words) {
            map.put(word, map.getOrDefault(word,0)+1);
        }
        PriorityQueue<Map.Entry<String,Integer>> priorityQueue = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue() != o2.getValue()) {
                    return o1.getValue()-o2.getValue();
                }else {
                    return -o1.getKey().compareTo(o2.getKey());
                }
            }
        });

        //Top-k问题
        for(Map.Entry<String, Integer> entry:map.entrySet()) {
            priorityQueue.add(entry);
            if(priorityQueue.size() > k) {
                priorityQueue.poll();
            }
        }

        List<String> list = new ArrayList<>();
        while (!priorityQueue.isEmpty()) {
            list.add(priorityQueue.poll().getKey());
        }
        Collections.reverse(list);
        return list;
    }
}